/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package geneticprogramming.algorithm;

import geneticprogramming.problem.Individual;
import geneticprogramming.problem.GEProblem;
import geneticprogramming.problem.GEProblemParams;

/**
 *
 * @author CJ
 */
public class GeneticAlgorithm {
    private GeneticAlgorithm(){}

    public static Individual run(GEProblemParams params,
                GEProblem problem){

        int populationSize = params.populationSize;
        int generationMax = params.generationMax;
        int displayFreq = params.displayFreq;
        int maxReMates = params.maxReMates;

        //2D array of all individuals
        Individual[] currentPopulation = problem.getRandomPopulation(populationSize);
//        System.out.println("Generated Initial Random Population.");

        //Get first run of fitness
        findFitness(currentPopulation, problem);
//        System.out.println("Set Fitness for all individuals.");

//        for(Individual one: currentPopulation)
//            System.out.println(one);

        //Internal state variable
        int generationCount = 1;

        while(true){
//            System.out.println("Starting generation: " + generationCount);
            double average = getFitnessAverage(currentPopulation);
            
            if(generationMax != -1 && generationCount==generationMax){
                //Must now return best individual
                Individual maxIndividual = currentPopulation[getMaxIndividual(currentPopulation)];
                System.out.println("--------------------------------------");
                System.out.println("Did not find an ideal individual.");
                System.out.println("Program terminated through reaching max generation.");
                System.out.println("Best individual had a fitness of: " + maxIndividual.getFitness()
                        + "/" + problem.getPerfectFitness() + '.');
                System.out.println("Average of last generation was: " + average + '.');
                return maxIndividual;
            }else if(generationCount % displayFreq == 0 && displayFreq!= -1){
                System.out.println("--------------------------------------");
                System.out.println("Generation Number: " + generationCount);
                System.out.println(currentPopulation[getMaxIndividual(currentPopulation)] + " was the best.");
                System.out.println("Average was " + average + ". Thats was out of a maximum of " + problem.getPerfectFitness() +'.');
                System.out.println("Mutation probabilty was 1/" + (1 + problem.getMutationProb(average)) + '.');
            }

            //Have Sex, thats weighted

            //Weighted Random Init
            CalculatedLookup calcLookup = new CalculatedLookup();
            calcLookup(currentPopulation, calcLookup, problem);

            //Weighted Recount init
            int countMax = Math.min((int)(problem.getPerfectFitness() - average + 1), maxReMates);

            //Might want to be sure that offspring are more fit
            Individual[] nextPopulation = new Individual[currentPopulation.length];

            int mutationProb = problem.getMutationProb(average);

            for(int i = 0; i< currentPopulation.length; ++i){
                int count = 0;
                double tempFitness = -1;
                Individual tempIndividual = null;
                while(tempFitness < average && count < countMax){
                    tempIndividual = problem.mate(currentPopulation[weightedRandom(calcLookup)],
                            currentPopulation[weightedRandom(calcLookup)]);

                    //Mutate from the damn sun
                    if((int)(Math.random() * (mutationProb + 1)) == 0)
                        tempIndividual = problem.mutate(tempIndividual);

                    tempIndividual.setFitness(problem.getFitness(tempIndividual));
                    tempFitness = tempIndividual.getFitness();
                    count++;
                }

                nextPopulation[i] = tempIndividual;

                if(tempIndividual.getFitness() == problem.getPerfectFitness()){
                    System.out.println("--------------------------------------");
                    System.out.println("Found perfect individual in generation " + generationCount);
                    System.out.println("This individual had a fitness of " + tempIndividual.getFitness() + " / " + problem.getPerfectFitness());
                    System.out.println("Thank you and have a good day.");
                    return tempIndividual;
                }
            }

            currentPopulation = nextPopulation;

            generationCount++;
        }
    }

    /*
     * This all works because you can fall in the gaps created between the fitnesses
     * . The bigger the fitness the bigger the gap.  Thats why that modified weighted
     * random binary search works.
     */
    protected static void calcLookup(Individual[] population, CalculatedLookup lookup, GEProblem fitness){
        double totalWeight = 0;
        lookup.lookup = new double[population.length];
        for(int i = 0; i < population.length; ++i){
//            double currentWeight = fitness.getFitness(population[i]);
            double currentWeight = population[i].getFitness();
            totalWeight += currentWeight;
            lookup.lookup[i] = totalWeight;
        }
        lookup.total = totalWeight;
    }

    /**
     * See above comment.
     * @return
     */
    protected static int weightedRandom(CalculatedLookup calcLookup){

        double[] lookup = calcLookup.lookup;
        double totalWeight = calcLookup.total;

        int probe = -1;
        int low = 0;
        int high = lookup.length - 1;

        double desired = Math.random() * totalWeight;

        while(low < high){
            probe = (low + high)/2;
            if(desired < lookup[probe]){
                high = probe - 1;
            }else if(desired > lookup[probe]){
                low = probe + 1;
            }else {
                //Highly likely
                low = probe;
                high = probe;
            }
        }

        if(low!=high){
            //Highly unlikely, means on the crack
            return probe;
        }else if(lookup[low] >= desired){
            //We passed it, pass ourselves
            return low;
        }else{
            //We are below, pass above
            return low+1;
        }
    }

    protected static void findFitness(Individual[] population, GEProblem fitness){
        for(int i = 0; i < population.length; ++i){
            population[i].setFitness(fitness.getFitness(population[i]));
        }
    }

    protected static double getFitnessAverage(Individual[] population){
        double total = 0;
        for(int i = 0 ;i < population.length; ++i)
            total += population[i].getFitness();
        return total/population.length;
    }

    protected static int getMaxIndividual(Individual[] population) {
        double max = population[0].getFitness();
        int maxIndex = 0;
        for (int i = 1; i < population.length; ++i) {
            if (population[i].getFitness() > max) {
                max = population[i].getFitness();
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}


  class CalculatedLookup {
    public double total;
    public double[] lookup;
}